/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-04-27
 * Time: 10:47
 */
public class Sort {
    /**
     * 插入排序算法
     *
     * @param array
     */
    public void InsertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            while (j >= 0) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
//                    array[j + 1] = tmp;
                    break;
                }
                j--;
            }
            array[j + 1] = tmp;
        }
    }


    /**
     * 希尔排序
     *
     * @param array
     */
    public void ShellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
    }

    private void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            while (j >= 0) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
//                    array[j + 1] = tmp;
                    break;
                }
                j -= gap;
            }
            array[j + gap] = tmp;
        }
    }

    /**
     * 堆排序
     *
     * @param array
     */
    public void HeapSort(int[] array) {
        //1.升序,建大根堆
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
        //2.第一个元素和最后一个元素交换
        int end = array.length - 1;
        while (end >= 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }
    }

    private void shiftDown(int[] array, int parent, int end) {
        int child = parent * 2 + 1;
        while (child < end) {
            //每次都要判断!!!
            if (child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 选择排序
     *
     * @param array
     */
    public void SelectSort(int[] array) {


        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    /**
     * 快速排序
     *
     * @param array
     */
    public void quickSort(int[] array) {
        quick(array, 0, array.length);

    }

    private void quick(int[] array, int start, int end) {

    }

    private int partition(int[] array, int left, int right) {

        return 1;
    }

    private void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
}
